#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e6+5;
int a[N],n,m,dis[N],vis[N];
vector<int>e[N];
inline int read(){
	int a=1,b=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') a=-a;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		b=(b<<1)+(b<<3)+(ch^48);
		ch=getchar(); 
	}
	return a*b;
}

inline void write(int x){
	if(x>9) write(x/10);
	putchar((x%10+'0'));
} 

inline void dij(int x){
	priority_queue<pii,vector<pii>,greater<pii> >q;
	for(int i=1;i<=n;i++) dis[i]=1e18;
	dis[x]=0;
	q.push({0,x});
	while(!q.empty()){
		int u=q.top().se;
		q.pop();
		if(vis[u]) continue;
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i];
			if(dis[u]+1<dis[v]){
				dis[v]=dis[u]+1;
				q.push({dis[v],v});
			}
		}
	}
} 

signed main(){
	
	freopen("oi.in","r",stdin);s
	freopen("oi.out","w",stdout);
	int c=read(),T=read();
	while(T--){
		n=read(),m=read();
		for(int i=1;i<=n;i++) e[i].clear();
		int uu,vv;
		for(int i=1,u,v;i<=m;i++){
			u=read(),v=read();
//			if(i==1) {uu=u,vv=v;continue;}
			e[u].push_back(v);
			e[v].push_back(u);
//			if()
		}
		if(c==3||c==4) printf("%lld 0\n",-(n-1)*2);
		else printf("%lld 0\n",-m-1); 
	}
	
	return 0;
}
